// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
//
// 示例:
//
// 输入: [0,1,0,3,12]
// 输出: [1,3,12,0,0]
//
// 说明:
//
//
// 必须在原数组上操作，不能拷贝额外的数组。
// 尽量减少操作次数。
//
// Related Topics 数组 双指针
// 👍 929 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

// Java：移动零
class P283MoveZeroes {
  public static void main(String[] args) {
    Solution solution = new Solution();
    // TO TEST
    int[] num = {0, 1, 0, 3, 12};
    solution.moveZeroes(num);
  }

  // leetcode submit region begin(Prohibit modification and deletion)
  static class Solution {
    /**
     * 题目要求将数组中的所有0元素放在数组后面，并保持 非0值的相对顺序不变。 最优的解法应该是时间复杂度O(n)且 空间复杂度为O(1)的解法，核心是，采用双索引
     * tag,index在[0,k]区间的所有元素为非0值，index用来遍历数组，交换0元素和非0元素，直至数组末尾。
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
      // tag 标记列表的位置
      // index 当前指向的数据的位置
      int tag = 0;
      int temp = 0;
      for (int index = 0; index < nums.length; index++)
        if (nums[index] != 0) {
          if (index != tag) {
            temp = nums[tag];
            nums[tag] = nums[index];
            nums[index] = temp;
          }
          tag++;
        }
      Arrays.stream(nums).forEach(System.out::print);
    }
  }
  // leetcode submit region end(Prohibit modification and deletion)

}
